/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

typedef struct TreeNode *DataType;

typedef struct {
    DataType *data;
    int size;
    int capacity;
} Queue;

int init(Queue *q)
{
    q->size = 0;
    q->capacity = 256;
    q->data = (DataType *)malloc(q->capacity * sizeof(DataType));
    return 0;
}

int destroy(Queue *q)
{
    free(q->data);
    q->size = 0;
    q->capacity = 0;
    return 0;
}

int add(Queue *q, DataType node)
{
    if (q->size == q->capacity) {
        DataType *tmp = (DataType *)malloc(2 * q->capacity * sizeof(DataType));
        memcpy(tmp, q->data, q->size * sizeof(DataType));
        free(q->data);
        q->data = tmp;
        q->capacity *= 2;
    }
    q->data[q->size] = node;
    q->size++;
    return 0;
}

DataType pop(Queue *q)
{
    if (q->size == 0) {
        return NULL;
    }

    DataType tmp = q->data[0];
    memmove(q->data, q->data + 1, (q->size - 1) * sizeof(DataType));
    q->size--;
    return tmp;
}

bool isSymmetric(struct TreeNode* root){
    Queue q;
    init(&q);

    add(&q, root);
    add(&q, root);

    while (q.size != 0) {
        DataType left = pop(&q);
        DataType right = pop(&q);
        if (left == NULL && right == NULL) {
            continue;
        }

        if (left == NULL || right == NULL) {
            return false;
        }

        if (left->val != right->val) {
            return false;
        }

        add(&q, left->left);
        add(&q, right->right);
        add(&q, left->right);
        add(&q, right->left);
    }

    destroy(&q);
    return true;
}
